package 二叉树

import "math"

/*
https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked

124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。
同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
*/

//func maxPathSum(root *TreeNode) int {
//	maxSum := math.MinInt32
//	var maxGain func(*TreeNode) int
//	maxGain = func(node *TreeNode) int {
//		if node == nil {
//			return 0
//		}
//		leftGain := max(maxGain(node.Left), 0) // 递归计算左右子节点的最大贡献值  只有在最大贡献值大于 0 时，才会选取对应子节点
//		rightGain := max(maxGain(node.Right), 0)
//		priceNewPath := node.Val + leftGain + rightGain // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
//
//		maxSum = max(maxSum, priceNewPath)         // 更新答案
//		return node.Val + max(leftGain, rightGain) // 返回节点的最大贡献值
//	}
//	maxGain(root)
//	return maxSum
//}

func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt32
	maxGain(root, &maxSum)

	return maxSum
}

func maxGain(node *TreeNode, maxSum *int) int {
	if node == nil {
		return 0
	}
	leftGain := max(maxGain(node.Left, maxSum), 0)
	rightGain := max(maxGain(node.Right, maxSum), 0)
	priceNewPath := node.Val + leftGain + rightGain

	*maxSum = max(*maxSum, priceNewPath)
	return node.Val + max(leftGain, rightGain)
}
